//
// Created by francklinson on 2021/11/27 AT 17:25.
// May Saint Diana bless you!
//

#include <iostream>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <algorithm>
#include <functional>
#include <climits>
#include <string>

using namespace std;

class Solution {
public:
    int binaryGap(int n) {
        int prev = -1; // 记录上一个1的位置
        int maxGap = 0;
        int pos = -1;  // 记录当前位置
        while (n) {
            ++pos;
            if (n & 1) {
                if (prev >= 0) {
                    maxGap = max(maxGap, pos - prev);
                }
                prev = pos;
            }
            n >>= 1;
        }
        return maxGap;
    }
};

int main() {
    Solution solution;
    cout << solution.binaryGap(22) << endl;
    cout << solution.binaryGap(5) << endl;
    cout << solution.binaryGap(6) << endl;
    cout << solution.binaryGap(8) << endl;
    cout << solution.binaryGap(1) << endl;
    return 0;
}

